﻿#include "queen_decomposition.h"
node::node(int x,int y,int problem_size)
{
    this->x=x;
    this->y=y;
    this->problem_size=problem_size;
    for(int a=0;a<problem_size;a++)
    {
        son.append(NULL);
    }
}

bool node::judge(int sum, int different, int x)
{
    if(x==this->x||different==this->x-y||sum==this->x+y)
        {
            return true;
        }
        else
        {
            return false;
        }
}

node::~node()
{
    if(parent!=NULL)
    {
        this->parent->son[x]=NULL;
    }
    for(int a=0;a<problem_size;a++)
    {
        if(son[a]!=NULL)
        {
            delete son[a];
        }
    }

}

queen_decomposition::queen_decomposition(int problem_size, int tasksize)
{
   this->problem_size=problem_size;
   this->task_size=tasksize;
    head_node=new node(-1,-1,problem_size);
    task_node.append(head_node);


}

queen_decomposition::~queen_decomposition()
{


}

QList<QStringList> queen_decomposition::decomposition_problem()
{
    while(task_node.size()<task_size&&task_node.isEmpty()==false)
    {
        create(task_node.first());
        task_node.removeFirst();
    }

   QList<QStringList> result;
   for(int a=0;a<task_node.size();a++)
   {
       result.append(get_pathdata(task_node[a]));
   }


   delete head_node;
    return result;
}

void queen_decomposition::create(node *p)
{
    for(int a=0;a<problem_size;a++)
       {
            if(a!=p->x)
            {
               node *q=new node(a,p->y+1,problem_size);
               q->parent=p;
               p->son[a]=q;
               if(tree_judge(q)==false)
               {

                   task_node.append(q);
               }
               else
               {
                   q->parent=NULL;
                   p->son[a]=NULL;
                   delete q;
               }
            }
        }
}


bool queen_decomposition::tree_judge(node *p)
{
    if(p!=NULL)
    {

    int sum=p->x+p->y;
    int different=p->x-p->y;
    int x=p->x;
    if(p->parent==head_node)
    {
        return false;
    }
    else
    {
        p=p->parent;
    }
    while(p!=head_node)
    {

        if(p->judge(sum,different,x)==true)
        {

            return true;
        }
        p=p->parent;
    }
    }
    else
    {
        qDebug()<<"节点判断出错，节点为空";
        exit(0);
    }

    return false;
}

QStringList queen_decomposition::get_pathdata(node *p)
{

        QStringList data;
        while(p!=head_node&&p!=NULL)
        {
            data.insert(0,QString::number(p->x));
            p=p->parent;
        }

        return data;
}


